Diplom- und Studienarbeiten

Einzelne Themenvorschläge

Die Anwendung von H-Kurven in der Bildkompression

Die Hilbertkurve wird u.A. zur Bildkompression eingesetzt. In der Arbeit "Towards Optimal Locality in Mesh-Indexings" [NRS97] wird eine neue Kurve (genannt H-Kurve) definiert und gezeigt, dass sie bessere lokalitätserhaltende Eigenschaften als die Hilbertkurve besitzt. Es soll nun untersucht werden, wie sich diese Verbesserung auswirkt, wenn H-Kurven zur Bildkompression verwendet werden.

Studienarbeit "Empirischer Vergleich von verschiedenen Lokalitätsmaßen für Gitterindizierungen"

Lokalität von Gitterindizierungen ist in vielen Anwendungen wie z.B. Bild- und Parallelverarbeitung von Wichtigkeit. In der Literatur gibt es verschiendene Ansätze der Messung von Lokalität. Diese verschiedenen Maße sollen für ausgewählte Gitterindizierungen (insbesondere raumfüllende Kurven) miteinander verglichen und bewertet werden.

Mehrdimensionale Hilbertkurven

Hilbertkurven sind sehr einfache raumfüllende Kurven mit für verschiedene Anwendungen sehr guten Lokalitätseigenschaften. Bislang konzentrierte sich das Hauptaugenmerk vorwiegend auf den zwei- und z.T. auch auf den dreidimensionalen Fall. Für Anwendungen wie Suchen in mehrdimensionalen Datenstrukturen sind aber auch mehrdimensionale Varianten der Hilbertkurve von Interesse. Aufbauend auf Teilen einer Studienarbeit soll die Beschreibung und Analyse (insbesondere in Bezug auf Lokalität) mehrdimensionaler Hilbertkurven vorangetrieben werden.

Erstellung eines interaktiven WWW-Manuskriptes zur Vorlesung "Kryptologie und Komplexität" mit Unterstützung durch Java-Applets

Die Vorlesung "Kryptologie und Komplexität" findet in allen ungeraden Sommersemestern statt. Die Anfänge eines zugehörigen interaktiven Skriptes sollen erweitert werden. Das Ziel ist, daß der Benutzer über WWW nicht nur passive Informationen erhält, sondern die beschriebenen Verfahren für selbst gewählte Eingaben ablaufen lassen kann. Dabei soll die Programmiersprache Java verwendet werden.

Studienarbeit ,,Visualisierung und Animation randomisierter Algorithmen''

In Bezug auf die Vorlesung ,,Randomisierte Algorithmen'' sollen einige Beispielalgorithmen (Spielbaumauswertung, 2SAT (Random Walks),...) zu Lehrzwecken (mit Java) illustriert werden. Dabei kann auf ein vorhandenes Skript zur Vorlesung aufgebaut werden.

Buchstabenerkennung mittels Arraygrammatiken

Bei der maschinellen Verarbeitung handschriftlich (in Blockbuchstaben) auszufüllender Formulare (wie sie heute in verschiedenen Bereichen üblich sind) stellt sich das Problem, möglichst viele solcher Formulare in möglichst kurzer Zeit mit größtmöglicher Sicherheit (Trefferquote) einzulesen. Wir wollen dieses Problem mit Hilfe von sog. Array-Grammatiken angehen. Eine solche Grammatik beschreibt dabei einen Buchstaben (bzw. eine Buchstabenvariante). Array-Grammatiken und ihre Anwendungen auf die Buchstabenerkennung wurden bislang vornehmlich von R. Freund und seinen MitarbeiterInnen an der TU Wien untersucht. In Fortführung dieser Forschungen sollen Programm(teile) erstellt werden, die die parallele Verarbeitung solcher Array-Grammatiken zur Buchstabenerkennung unterstützen.

Formalsprachliche Aspekte der Symmetrie

Symmetrie wurde als Konzept "zwischen Nichtdeterminismus und Determinismus" in der Komplexitätstheorie von Lewis und Papadimitriou (Theoretical Computer Science 19:161-187, 1982) eingeführt; hierbei wird die Symmetrie der Konfigurationsübergangsrelation bei Turingmaschinen gefordert. Das neu entfachte Interesse an diesem Begriff zeigt sich u.a. am Beweis des Komplementabschlusses von symmetrischem LOGSPACE (Chicago Journal of Theoretical Computer Science, Juni 1995) und an den Zusammenhängen mit Fragen des reversiblen Rechnens (LNCS 583, S. 401 ff.), die möglicherweise eine Lösung für das Entropieproblem bei Höchstleistungsrechnern andeuten. Jüngst wurde der Versuch unternommen, diesen Begriff auf endliche Automaten, Zählerautomaten und lineare Grammatiken zu übertragen (Electronic Colloquium on Computational Complexity TR96-039, siehe http://www.eccc.uni-trier.de:/pub/eccc/). Die so definierten Sprachklassen scheinen ungewöhnliche Abschlußeigenschaften zu besitzen, und auch die hierarchischen Beziehungen sind noch ungeklärt.

Datenunabhängigkeit bei verschiedenen Automatenmodellen

Das Konzept der Datenunabhängigkeit wurde z.B. für endliche (Mehrkopf-)Automaten von M. Holzer untersucht. Für nahezu alle anderen Automatenmodelle wurden solche Betrachtungen bislang nicht angestellt. Diese Aufgabe stellt sich mithin.

Rekursiv zerlegbare Probleme

Rekursive Zerlegbarkeit von Problemen beschreibt auf formale Weise wünschenswerte Parallelisierungseigenschaften von Problemen. Dabei scheint es enge Bezüge zum Divide and Conquer-Paradigma zu geben, die näher untersucht werden sollen. Weiter soll auch eine Verallgemeinerung des Konzeptes der rekursiven Zerlegbarkeit angedacht werden. Hier kann auf bereits existierende Vorarbeiten (Dissertation) aufgebaut werden.

This page was last updated on Juli 24th, 1997 by P. Meißner